import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author lilongkang
 * @version 1.0
 * @description: TODO
 * @date 2024/3/14 12:12
 */
public class LevelOrder {
    public static void main(String[] args) {
        TreeNode root = TreeNode.InitTree(new Integer[]{3, 9, 20, null, null, 15, 7});
        System.out.println(bfsOrder(root));
        System.out.println(bfs(root));
        System.out.println(dfsOrder(root));
        List<Integer> result = new ArrayList<>();
        dfs(result,root);
        System.out.println(result);
    }

    /**
     * BFS(Breadth First Search)
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> bfsOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//存储每层的节点。初始时只有root根节点，不包含子节点。
            List<Integer> levelResult = new ArrayList<>();
            // 遍历每层节点
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur == null) {
                    continue;
                }
                levelResult.add(cur.val);
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            if (!levelResult.isEmpty()) {
                result.add(levelResult);
            }
        }
        return result;
    }

    public static List<Integer> bfs(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode poll = queue.poll();
            result.add(poll.val);
            if(poll.left!=null){
                queue.offer(poll.left);
            }

            if(poll.right!=null){
                queue.offer(poll.right);
            }
        }
        return result;
    }

    /**
     * 本题使用 DFS 同样能做。由于题目要求每一层的节点都是从左到右遍历，因此递归时也要先递归左子树、再递归右子树。
     * DFS 做本题的主要问题是： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾。
     * 当遍历到一个新的深度 level，而最终结果 res 中还没有创建 level 对应的列表时，应该在 res 中新建一个列表用来保存该 level 的所有节点。
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> dfsOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, root, 0);
        return result;
    }

    private static void dfs(List<List<Integer>> res, TreeNode node, int level) {
        if (res.size() - 1 < level) {
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(node.val);
        if (node.left != null) {
            dfs(res, node.left, level + 1);
        }
        if (node.right != null) {
            dfs(res, node.right, level + 1);
        }
    }

    public static void dfs(List<Integer> res,TreeNode root){
        if(root == null){
            return;
        }
        res.add(root.val);
        dfs(res,root.left);
        dfs(res,root.right);
    }
}
